/**
 * @Classname DivideAndConquer 分治算法
 * @Description 二分搜索、大整数乘法、棋盘覆盖、合并排序、快速排序
 * 线性时间选择、最接近点对问题、循环赛日程表
 * 最佳实践：汉诺塔 A->C 小的在上面 总共要多少步
 * 1、分解为多个相互独立的子问题
 * 2、子问题解决或者子问题递归拆分成更小问题解决
 * 3、合并
 * @Date 2021/12/23 13:43
 */
public class DivideAndConquer {

    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');
    }
    //汉诺塔的移动问题：分治算法 这里的num为盘的编号
    public static void hanoiTower(int num,char a, char b, char c){
        if (num ==1){
            System.out.println("第1个盘从"+a+"->"+c);
        }else {
            //最下面的盘和上面所有的盘
            hanoiTower(num-1,a,c,b);
            System.out.println("第"+num+"个盘从"+a+"->"+c);
            hanoiTower(num-1,b,a,c);
        }
    }
}
